
// 链表
// 链表的概念及结构
//         链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的


import java.util.List;

// ListNode 代表一个节点，以节点的特性，去抽象出一个类
class ListNode{
     public int val;// 值域
     public ListNode next;
     // 因为 引用next 存储的是下一个节点的地址，那么引用的类型也应当是节点类型
    public ListNode(int val){// 创建 一个 构造方法
        this.val = val;
    }
}


public class MyLinkedList {
    public ListNode head;// 链表的头引用

    public void createList(){
        ListNode listNode1 = new ListNode(12);
        ListNode listNode2 = new ListNode(23);
        ListNode listNode3 = new ListNode(23);
        ListNode listNode4 = new ListNode(23);
        ListNode listNode5 = new ListNode(56);

        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;
        this.head = listNode1;
    }
    public void display(){
        ListNode cur = this.head;
        while(cur!=null){
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();// 换行
    }

    //查找关键字key是否在单链表当中
    public boolean contains(int key){
        ListNode cur = this.head;
        while(cur!=null){
            if(cur.val==key){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }
    //得到单链表的长度(带头不算头节点，不带头算头节点)
    public int size(){
        int count=0;
        ListNode cur = this.head;
        while(cur!=null){
            count++;
            cur=cur.next;
        }
        return count;
    }

    //头插法
        public void addFirst(int data){
           ListNode node = new ListNode(data);
           node.next = this.head;
           this.head = node;
        }

         //尾插法
        public void addLast(int data){
             ListNode node = new ListNode(data);
             if(this.head == null){
               this.head = node;
             }else{
                 ListNode cur = this.head;
                 while(cur.next!=null){
                     cur = cur.next;
                 }
                 cur.next = node;
             }

        }
        //任意位置插入数据节点
        public void addIndex(int index,int data){
             if(index<0 || index>size()){
                 System.out.println("插入数据节点的位置不合法");
                 return;
             }
             if(index==0){
                 addFirst(data);// 调用头插
                 return;
            }
             if(index== size()){
                 addLast(data);
                 return;
             }
              ListNode cur = findIndex(index);
              ListNode node = new ListNode(data);
              node.next = cur.next;
              cur.next = node;

        }
        // 找到index-1位置的节点位置
        // 跟图解解释的一样，如果你要插入一个位置，你就需要找它的前一个节点的位置
        // 而我们是链表没有下标，所以返回是 前一个节点的地址
        public ListNode findIndex(int index){
              ListNode cur = this.head;
            while(index-1 != 0){
                cur = cur.next;
                index--;
            }
            return cur;
        }

         //删除第一次出现关键字为key的节点
        public void remove(int key){
        if(this.head == null){// head为空
            System.out.println("链表为空，无数字可删除！");
            return;
        }
        if(this.head.val == key){// 判断头节点是为删除数字
            this.head = this.head.next;
            return;
        }
        ListNode cur = searchPrev(key);// 找到删除节点的前一个节点
        if(cur == null){
            System.out.println("没有你要删除元素");
            return;
        }
        ListNode del = cur.next;// 要删除的节点地址
        cur.next =  del.next;// 删除节点

        }
        // 寻找删除节点的前一个节点（key的前驱）
        public  ListNode searchPrev(int key){
          ListNode cur = this.head;
          while(cur.next != null){
              if(cur.next.val == key)
              {
                  return cur;
              }
              cur = cur.next;
          }
          return null;// 表示没找到
        }

        //删除所有值为key的节点
        public ListNode removeAllKey(int key){
              if(this.head == null){
                  return null; // 防止后面的cur出现空指针错误
              }
              ListNode prev = this.head;
              ListNode cur = this.head.next;
              while(cur!=null){
                  if(cur.val == key){
                      prev.next = cur.next;
                      cur=cur.next;
                  }else{
                       prev = cur;
                       cur=cur.next;
                  }
              }
              // 最后处理头
              if(this.head.val==key){
                  this.head = this.head.next;
              }
              return head;
        }

//        public void display();// 已经实现了

    // 清楚链表的所有的节点
        public void clear(){
        // this.head = null; 粗暴方法
            while(this.head!=null){
                ListNode headNext = head.next;
                this.head.next = null;
                this.head = headNext;
            }
        }

}





